class unionFind:
    def __init__(self,grid):
        row = len(grid)
        col = len(grid[0])
        self.root = [-1] * (row * col)
        for i in range(row * col):#初始化，每个节点的父节点都是自己
            self.root[i] = i
    def find(self,x):
        if x == self.root[x]:#找到祖先节点
            return self.root[x]
        else:#压缩路径，每个节点到祖先节点的长度为1
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def union(self,x,y):
        rootX = self.find(self.root[x])#找到x的祖先
        rootY = self.find(self.root[y])#找到y的祖先
        if rootX != rootY:
            self.root[rootY] = rootX#x的祖先指向y的祖先
